Routers and layer-3 switches read an IP address of packets and route the packets according to destination address. The packet is received on an incoming link of the router. The router selects an outgoing link or next hop based on the destination address. When a packet is routed from a computer in California to a computer in Michigan, multiple routers typically receive and forward the packet. Each router in the path is also referred to as a hop. For most of the routers along the path, only the network part of the destination address is used to route the packet.
The router typically employs a forwarding table that includes a next hop pointer for IP addresses. The forwarding table includes two types of IP addresses: individual host IP addresses and network IP addresses. A host IP address designates one host computer. Host IP addresses are fully specified. An IPv4 host address specifies 32 bits, while an IPv6 host IP address specifies 128 bits.
A network (subnet) IP address aggregates one or more consecutive host IP addresses. Network IP addresses are specified by a prefix. For example, the IPv4 network IP address 0x123456/24 specifies all host IP addresses in the range [0x12345600, 0x123456FF]. When a packet arrives, the router looks up the IP addresses stored in the forwarding table using the packet's destination IP address. The router finds the most specific IP address according to a LPM (Longest Prefix Match) criteria. The router forwards the packet to the next hop associated with this address.
The LPM criteria states that when the search yields multiple matches (i.e. the searched IP address is contained in several subnets), the packet should be routed to the next hop associated with the network address having the longest prefix. For example, given the IPv4 forwarding table [0x123456/24, 3]; [0x1234567/28, 2]; [0x12345678, 1], a packet with destination IP address 0x12345666 is forwarded to 3 (having only one matching subnet address). A packet with destination address 0x12345677 is forwarded to 2 (having 2 matching subnet addresses and selecting the one with longest matching prefix). A packet with destination address 0x12345678 is forwarded to 1 (having 3 matching subnets and selecting the one with the longest matching prefix).
Operating or routing speed and the cost of the router hardware are very important to router design. If the forwarding table includes a next hop pointer for each individual host IP address, the forwarding table would have 232 entries for a 32-bit IPv4 addresses and 2128 entries for a 128-bit IPv6 addresses. The search time would be too long and the amount of memory too large. To compress the forwarding table and increase speed, the forwarding table is frequently arranged using network IP addresses.